//package leetcode.hot100.intermediate;
//
//import java.util.ArrayList;
//import java.util.List;
//
//class Solution {
//    public List<String> generateParenthesis(int n) {
//        List<String> ans = new ArrayList<String>();
//        backtrack(ans, new StringBuilder(), 0, 0, n);
//        return ans;
//    }
//
//    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
//        if (cur.length() == max * 2) {
//            ans.add(cur.toString());
//            return;
//        }
//        if (open < max) {
//            cur.append('(');
//            backtrack(ans, cur, open + 1, close, max);
//            cur.deleteCharAt(cur.length() - 1);
//        }
//        if (close < open) {
//            cur.append(')');
//            backtrack(ans, cur, open, close + 1, max);
//            cur.deleteCharAt(cur.length() - 1);
//        }
//    }
//}
//
//
//public class Test5 {
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        List<String> res = solution.generateParenthesis(3);
//        System.out.println(res);
//    }
//}
